package LeetCode_1_100;

class Solution04 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if (total % 2 == 1) {
            return findKth(nums1, nums2, 0, 0, total / 2 + 1);
        } else {
            int left = findKth(nums1, nums2, 0, 0, total / 2);
            int right = findKth(nums1, nums2, 0, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
    }

    private int findKth(int[] A, int[] B, int aStart, int bStart, int k) {
        if (aStart >= A.length) return B[bStart + k - 1];
        if (bStart >= B.length) return A[aStart + k - 1];
        if (k == 1) return Math.min(A[aStart], B[bStart]);

        // 计算有效步长（防止越界）
        int aStep = Math.min(k / 2, A.length - aStart);
        int bStep = Math.min(k / 2, B.length - bStart);
        int aIndex = aStart + aStep - 1;
        int bIndex = bStart + bStep - 1;

        // 比较并排除较小值的区间
        if (A[aIndex] <= B[bIndex]) {
            return findKth(A, B, aStart + aStep, bStart, k - aStep);
        } else {
            return findKth(A, B, aStart, bStart + bStep, k - bStep);
        }
    }
}

public class LeetCode04_findMedianSortedArrays  {
    public static void main(String[] args) {
        Solution04 solution = new Solution04();
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println(solution.findMedianSortedArrays(nums1, nums2));
    }
}
